#pragma once

#include "Scene.hpp"

const uint KD_TREE_MAX_DEPTH = 8;

class KDObjLink
{
public:
	SceneObject *Obj;
	KDObjLink *NextObjLink;
};

class KDNode
{
public:
	uint Level;
	KDNode *Parent, *Children[2];
	common::BOX Box;
	KDObjLink *FirstObjLink;
};

class KDTree
{
public:
	KDTree(common::BOX &WorldBox);
	~KDTree();

	const common::BOX & GetWorldBox() { return m_RootNode->Box; }
	uint GetNodeCount() { return m_NodePool.GetUsedCount(); }
	const uint * GetNodesPerLevel() { return m_NodesPerLevel; }
	const uint * GetObjectsPerLevel() { return m_ObjectsPerLevel; }
	const KDNode * GetRootNode() { return m_RootNode; }

	void InsertObject(SceneObject *obj);
	void RemoveObject(SceneObject *obj);
	void ObjectTransformChange(SceneObject *obj);

	void ListObjectsIntersectingFrustum(SceneObjectPtrVector &out, const common::FRUSTUM_PLANES &Frustum, SceneObjectPredicate *Pred = NULL);
	void ListObjectsIntersectingSweptBox(SceneObjectPtrVector &out, const common::BOX &box, const common::VEC3 &boxDir, SceneObjectPredicate *Pred = NULL);
	//void ListObjectsIntersectingBox(SceneObjectPtrVector &out, const common::BOX &Box, SceneObjectPredicate *Pred = NULL);
	void ListObjectsIntersectingSphere(SceneObjectPtrVector &out, const common::VEC3 &sphereCenter, float sphereRadius, SceneObjectPredicate *pred = NULL);

private:
	common::DynamicFreeList<KDNode> m_NodePool;
	common::DynamicFreeList<KDObjLink> m_ObjLinkPool;
	KDNode *m_RootNode;
	uint m_NodesPerLevel[KD_TREE_MAX_DEPTH], m_ObjectsPerLevel[KD_TREE_MAX_DEPTH];

	KDNode * AllocNode() { return m_NodePool.TryNew(); }
	void FreeNode(KDNode *node) { m_NodePool.Delete(node); }

	KDObjLink * AllocObjLink() { return m_ObjLinkPool.TryNew(); }
	void FreeObjLink(KDObjLink *objLink) { m_ObjLinkPool.Delete(objLink); }

	void AddObjectToNode(KDNode *node, SceneObject *obj);
	void RemoveObjectFromNode(KDNode *node, SceneObject *obj);
	void DeleteObjLink(KDNode *node, KDObjLink *prevLink, KDObjLink *currLink);
	void CalcOptimalSplit(uint *outNormalAxisIndex, float *outSplitV, KDNode *node);
	void SplitNode(KDNode *node);
	void TryMergeNode(KDNode *node);
	void MergeNode(KDNode *node);
	bool IsNodeLeaf(KDNode *node) { return node->Children[0] == NULL; }
	uint GetNodeObjectCount(KDNode *node);
	KDNode * FindNodeForObject(const common::BOX &objWorldBox);
	void CalcNodeObjectBoundingBoxesMeanAndVariance(common::VEC3 *outMean, common::VEC3 *outVariance, KDNode *node);
	void CalcNodeObjectPositionsMeanAndVariance(common::VEC3 *outMean, common::VEC3 *outVariance, KDNode *node);
	void TransferObjectsToChildNodes(KDNode *node);
	void ValidateTree() { ValidateNode(m_RootNode); }
	void ValidateNode(KDNode *node);
	void AddObjectsIntersectingFrustum(SceneObjectPtrVector &out, KDNode *node, const common::FRUSTUM_PLANES &Frustum, SceneObjectPredicate *Pred);
	void AddObjectsIntersectingSweptBox(SceneObjectPtrVector &out, KDNode *node, const common::BOX &box, const common::VEC3 &boxDir, SceneObjectPredicate *Pred);
	void AddObjectsIntersectingSphere(SceneObjectPtrVector &out, KDNode *node, const common::VEC3 &sphereCenter, float sphereRadius, SceneObjectPredicate *pred);
};
